package com.zhanghp.class030;

/**
 * 数组中有2种数出现了奇数次，其他的数都出现了偶数次
 * 返回这2种出现了奇数次的数
 * 测试链接 : https://leetcode.cn/problems/single-number-iii/
 *
 * @author zhanghp
 * @since 2024/4/3 17:14
 */
public class Code05_DoubleNumber {

    static class Solution {
        public int[] singleNumber(int[] nums) {
            int eor1 = 0;
            for (int num : nums) {
                eor1 ^= num;
            }
            int rightOne = extractRightOne(eor1);


            int eor2 = 0;
            for (int num : nums) {
                // 写 == 1有问题，因为 &运算后，二进制的1不一定在第一位
                if ((num & rightOne) == 0) {
                       eor2 ^= num;
                }
            }
            return new int[]{eor2, eor2 ^ eor1};
        }

        /**
         * Brian Kernighan算法
         * 提取出二进制里最右侧的1
         *
         * @param i
         * @return
         */
        public int extractRightOne(int i){
            return i & -i;
        }
    }

}
